package 我的Java学习_算法基础.day_06;

public class _096_欧几里得算法的扩展集合 {
    static long x;
    static long y;
    public static long gcd(long m,long n){
        return n==0?m:gcd(n,m%n);
    }
    /**
     * 最小公倍数 lowest common multiple
     */
    public static long lcm(long a,long b){
        return a*b/gcd(a,b);
    }

    /**
     * 扩展欧几里得
     * 调用完成后x、y是ax+by=gcd(a,b)的解
     * @param a
     * @param b
     * @return 最大公约数
     */
    public static long ext_gcd(long a,long b){
        if(b==0){
            x=1;
            y=0;
            return a;
        }
        long res = ext_gcd(b,a%b);
        //x,y已经被下一层递归更新了
        long x1 = x;//备份x
        x=y;//更新x
        y=x1-a/b*y;//更新y
        return res;
    }

    /**
     * 求ax+by=m 的解
     * @param a
     * @param b
     * @param m
     * @throws Exception
     */
    public static long linearEquation(long a,long b,long m)throws Exception{
        long d = ext_gcd(a,b);
        //m不是gcd（a,b）的倍数，这个方程无解
        if(m%d!=0) throw new Exception("无解");
        long n = m/d;
        x*=n;
        y*=n;
        return d;
    }
    /**
     * 求逆元
     * ax%n=1中的x
     * @param a
     * @param mo
     * @return
     * @throws Exception
     */
    public static long inverseElement(long a,long mo) throws Exception{
        long d = linearEquation(a,mo,1);
        x=(x%mo+mo)%mo;//保证x>0
        return d;
    }
    /**
     * x=a1(%m1)
     *  =a2(%m2)
     *  =a3(%m3)
     *  x=a1+m1y1   (1)
     *  x=a2+m2y2
     *  ==>m1y1+m2y2=a2-a1是一个线性方程
     *  可解出y1 linearEquation(m1,-m2,a2-a1)
     *  带回（1），得到特解x0 = a1+m1*y1--->x=x0+k*lcm(m1,m2)
     *  得到一个新方程 x = x0(mod lcm(m1,m2))
     */

    /**
     *
     * @param a 余数的数组
     * @param m 模的数组
     * @return  方程组的解
     * @throws Exception
     */
    public static long linearEquationGroup(long[] a,long[] m)throws Exception{
        int len = a.length;
        if(len==0&&a[0]==0) return m[0];
        for(int i =1;i<len;i++) {
            //这里往前看是两个方程
            long a2_a1 = a[i] - a[i - 1];
            long d = linearEquation(m[i - 1], -m[i], a2_a1);
            //现在的x是y1,用y1求得一个特解
            long x0 = a[i - 1] + m[i - 1] * x;
            long lcm = m[i - 1] * m[i] / d;
            a[i] = (x0 % lcm + lcm) % lcm;
            m[i] = lcm;
        }
        //合并完成后，只有一个方程：x = a[len-1](%m[len-1])
        return a[len-1]%m[len-1];
    }
}
